package com.yangli.leecode.mashib.interview;

import java.util.*;

/**
 * @Description
 * @Author liyang
 * @Date 2023/4/12 17:46
 */
public class Seventy {



    //数组排序之后，用双指针找到差距最小的那个
    public static int min(int[] arr, int[] site){
        Arrays.sort(arr);
        Arrays.sort(site);
        int ans = 0;
        for (int i = 0, j = 0; i < arr.length; i++) {
            //后值大于前面的值，表示当前的值已经是较小的那个  已经找到当前最小的差值了
            if (j == site.length - 1 || Math.abs(site[j] - arr[i]) < Math.abs(site[j + 1] - arr[i])) {
                ans = Math.max(ans, Math.abs(site[j] - arr[i]));
                continue;
            }
            //相等或者小于前置，则向后查找
            j++;
        }
        return ans;
    }


    //第一种方法就暴力解，n^2复杂度
    //最优解：查找第k小，要有这个敏感度。如果能知道数据的最大范围，求第k小就是求小于n有多少个的二分函数。
    public static int kthAbs(int[] arr, int k){
        int n = arr.length;
        if (n < 2 || k < 1 || k > (n * (n - 1) >> 1)) {
            return -1;
        }
        Arrays.sort(arr);
        int ans = -1;//如果数组全部相当，应该返回0
        //差值范围应该是在最大和最小之间 先二分查找
        int left = 0;
        int right = arr[n - 1] - arr[0];
        int mid = 0;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (countValue(arr, mid) < k) {//说明第k小的数字在右边，但是最近的肯定是在最左边
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans + 1;//第k小数为n,差值可能为重复，只能找到最左边的数。
    }


    //数组终的差值小于等于value的有多少个
    public static int countValue(int[] arr, int value){
        int ans = 0;

        for (int l = 0, r = 1; l < arr.length; r = Math.max(r, ++l)) {//r和l不能相等，计算的是差值   r = Math.max(r,++l)==>每次l左指针都会增加，都是右指针一定是比左指针大
            while (r < arr.length && arr[r] - arr[l] <= value) {
                r++;
            }
            ans += r - l - 1;


        }
        return ans;
    }


    //子子序列是等差数列的个数
    public static int numberOfAS(int[] arr){
        int n = arr.length;
        int ans = 0;
        ArrayList<Map<Integer, Integer>> arrayList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> temp = new HashMap<>();
            arrayList.add(temp);//每次以i为结尾，跟前面每次数值形成的差值，在前面的数组中出现的次数
            for (int j = i - 1; j > 0; j--) {
                long diff = (long) arr[i] - (long) arr[j];//边界处理
                if (diff <= Integer.MIN_VALUE || diff >= Integer.MAX_VALUE) {
                    continue;//差值过大不可能产生等差数列
                }
                int count = arrayList.get(j).getOrDefault(arr[i] - arr[j], 0);
                ans += count;//超过2才能算一个等差数列
                temp.put(arr[i] - arr[j], count + 1);

            }
        }
        return ans;
    }


    interface Robot {
        public boolean move();//flase不能移动 true能移动并且向前移动一步

        public void turnLeft();

        public void turnRight();

        public void clean();
    }

    //dfs 深度优先遍历
    public static void cleanRoom(Robot robot){
        clean(robot, 0, 0, 0, new HashSet<>());//机器人从0。0位置开始，深度d，已经访问过的位置x_y==visited
    }

    //向每个方向移动 xy变动规律 上 右 下 左
    private static final int[][] ds = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public static void clean(Robot robot, int x, int y, int d, HashSet<String> visited){
        robot.clean();
        visited.add(x + "_" + y);
        //从自身四个方向遍历，每个方向深度递归
        for (int i = 0; i < 4; i++) {
            int nd = (i + d) % 4;//开始方向为0，责下一个方向分别为0123 当前方向3，则下一个方向为3012
            int nx = ds[nd][0] + x;
            int ny = ds[nd][1] + y;
            if (!visited.contains(nx + "_" + ny) && robot.move()) {
                clean(robot, nx, ny, nd, visited);
            }
            robot.turnRight();
        }
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    }

    public static void main(String[] args){

        int[] temp = new int[]{4, 11, 20, 23, 30};
        //System.out.println(Seventy.countValue(temp, 3));
/*
        System.out.println(Seventy.minEatingSpeed(temp, 5));
        System.out.println(Seventy.minEatingSpeed(temp, 6));
        System.out.println(Seventy.minEatingSpeed(temp, 7));
        System.out.println(Seventy.minEatingSpeed(temp, 8));

        System.out.println(Seventy.minEatingSpeed(temp, 20));
        System.out.println(Seventy.minEatingSpeed(temp, 30));*/
        //System.out.println(Seventy.minEatingSpeed(temp, 6));

/*        int[] temp2 = new int[]{332484035,524908576,855865114,632922376,222257295,690155293,112677673,679580077,337406589,290818316,877337160,901728858,679284947,688210097,692137887,718203285,629455728,941802184};
        Arrays.sort(temp2);
        System.out.println(Seventy.minEatingSpeed(temp2, 823855818));*/
        int[] temp3 = new int[]{ 805306368, 805306368, 805306368};
        System.out.println(Seventy.minEatingSpeed(temp3, 1000000000));

        System.out.println(Seventy.eatSpeeding(temp3, 1,1000000000));

    }
    //找出最大和最小 max和1，每个判断用这个速度是否能吃完，找到最优解
    public static int minEatingSpeed(int[] piles, int h){
        int n = piles.length;
        Arrays.sort(piles);
        int left = 1;
        int right = piles[n - 1];
        int mid = 0;
        int ans = piles[n - 1];
        while (left <= right) {
            mid = (left + right) >> 1;
            if (eatSpeeding(piles, mid, h)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public static boolean eatSpeeding(int[] arr, int speed, int h){
        long ans = 0;//[805306368, 805306368, 805306368] speed:1 h:1000000000 如果用int ans和大于最大值了==》long
        int offset = speed - 1;
        for (int i = 0; i < arr.length; i++) {
            ans += (arr[i] + offset) / speed;
        }
        return ans <= h;
    }

}
